//
// Description: 576. 出界的路径数
// Created by Loading on 2021/8/15.
//

#include <bits/stdc++.h>

using namespace std;

/* DFS记忆化搜索 */
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
    const int MOD = 1e9 + 7;
    // dp 记忆化数组，dp[i][j][k] 表示在坐标 (i,j) 处，剩余 k 步的情况下可以出界的路径数，初始化为 -1
    vector<vector<vector<int>>> dp(55, vector<vector<int>>(55, vector<int>(55, -1)));

    // DFS 方法
    function<long long(int, int, int)> dfs = [&](int i, int j, int k) {
        // 可以出界
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return 1;
        }
        // 步数已用尽，未出界
        if (k == 0) {
            return 0;
        }
        // 此状态已遍历，直接取用
        if (dp[i][j][k] != -1) {
            return dp[i][j][k];
        }
        int move_remain = k - 1;
        // 四个方向搜索，和为当前状态的路径数
        dp[i][j][k] = (dfs(i - 1, j, move_remain) + dfs(i + 1, j, move_remain) + dfs(i, j - 1, move_remain) +
                      dfs(i, j + 1, move_remain)) % MOD;
        return dp[i][j][k];
    };

    return dfs(startRow, startColumn, maxMove);
}

int main() {
    int m = 50, n = 50, maxMove = 50;
    int startRow = 20, startColumn = 30;
    int res = findPaths(m, n, maxMove, startRow, startColumn);
    cout << res << endl;
}